#include <stdio.h>
#include "single_linked_list.cpp"

// 链表是否成环 若成环返回入口

LNode *IsCircle(LinkedList &L) {
	if (L == NULL)
		return NULL;
	
	if (L->next == L)
		return L;

	LNode *fast = L->next->next, *slow = L->next;
	
	while (fast != slow) {
		if (fast == NULL || slow == NULL)
			return NULL; // 不成环
		fast = fast->next->next;
		slow = slow->next;
	}

	// 找入口
	LNode *ptr = L;
	while(ptr != slow){
		ptr = ptr->next;
		slow = slow->next;
	}

	return ptr;
}

int main() {
	LinkedList L;
    InitList(L);

    // 插入
    ListAppend(L, 2);
    ListAppend(L, 5);
    ListAppend(L, 9);
    ListAppend(L, 7);
    ListAppend(L, 3);
    ListAppend(L, 6);
    PrintList(L);

	GetElem(L,6)->next = GetElem(L,1);
	LNode *res = IsCircle(L);
	if (res != NULL)
		printf("===>res: %d", res->data);
	else
		printf("不成环");
	return 0;
}
